//
// Created by PC on 2023/8/6.
/*
 * https://oj.youdao.com/problem/15384?from=contest
 * 有道小图灵
(编程思维赛项-C++普及组)
第三题《小图灵的新游戏》
小图灵的新游戏
题目描述
小图灵新入手了一款PS333平台的游戏，在游戏中从起点到终点共有n个得分点，编号为1-n,需要使用灵能手套才能获得得分点分数，灵能手套经过充能后只可以使用3次。
游戏最终成绩的计算规则如下：假设通过灵能手套获取了三个不同的编号分别为i,j,k的得分点的分数ai,aj,ak,最终成绩为3个得分点分数总和先减去所选取三点中编号最小值再减去所选取三点中编号最大值，即ai+aj+ak-min(i,j,k)-max(i,j,k)。
请你编写程序帮助小图灵获得最好成绩。
注：min(i,j,k)表示i,j,k中的最小值，max(i,j,k)表示i,j,k中的最大值。
输入描述
第一行包含一个整数t,表示有t组测试数据；每组测试数据包含两行：
第一行包含一个整数n,表示游戏中得分点的数量；
第二行包含n个整数，表示从起点到终点n个得分点的分数，第i个得分点的分数为ai
输出描述每组测试数据一行，输出小图灵所能够获得的最好成绩。
样例1
输入
1
6
122333
输出
1
样例2
输入
2
6
1913427711
8
87654321
输出
54
17
样例3
输入
1
10
12399910101010
输出
17
提示
对于20%的数据：1≤t≤10,3≤n≤100;
对于60%的数据：1≤t≤20,3≤n≤10³;
对于100%的数据：1≤t≤100,3≤n≤10⁵,1≤a;≤10^8。输入文件的大小不超过10MB。
时间限制：1000ms内存限制：256MB
 * */
// 满分版本 通过预处理 将j点左边和右边的最大值提前计算出来
//


#include <iostream>

using namespace std;


int main()
{
//    1e9 = 1*10^9 目的是初始化一个极大值, 1e10就溢出了;
    int t, n,inf=1e9;
    cin >> t;
    while (t--)
    {
        long long ans = -1;
        cin >> n;
        long long l[n + 1];
        // left:保存j点左边的l[i]-i的最大值 right:保存j点右边的l[k]-k的最大值
        long long left[n + 1], right[n + 1];
//        int sum = 0,cur;
        for (int m = 1; m <= n; ++m)
            cin >> l[m];
        left[0]=right[n+1]=-inf;
        for (int m = 1; m <=n ; ++m)
            left[m]=max(left[m-1],l[m]-m);
        for (int m = n; m >=1 ; --m)
            right[m]=max(right[m+1],l[m]-m);
        // 遍历中间点j, 根据左left右right的最大值,计算哪个j能够满足最大值
        // 数据是从1开始到n结束, 所以作为中间点要从2到n-1遍历
        for (int j = 2; j < n; ++j)
        {
            ans=max(ans,l[j]+left[j-1]+right[j+1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}